public class num21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1 == null){
//            return list2;
//        }
//        if(list2 == null){
//            return list1;
//        }
//        if(list1.val <= list2.val){
//            list1.next = mergeTwoLists(list1.next,list2);
//            return list1;
//        }
//            list2.next = mergeTwoLists(list1,list2.next);
//            return list2;
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode dummyhead = new ListNode();
        ListNode prev = dummyhead;
        ListNode prev1 = list1;
        ListNode prev2 = list2;
        while (prev1 != null && prev2 != null) {
            if (prev1.val <= prev2.val) {
                prev.next = prev1;
                prev1 = prev1.next;
                prev = prev.next;
            } else {
                prev.next = prev2;
                prev2 = prev2.next;
                prev = prev.next;
            }
        }
        if(prev1 == null){
            prev.next = prev2;
        }
        if(prev2 == null){
            prev.next = prev1;
        }
        return dummyhead.next;
    }
}
